#include<bits/stdc++.h>

using namespace std;
using ll=long long;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

/**
 * 用定义法去计算phi(n):1~n中与n互质的元素个数  p,q互质<=>gcd(p,q)=1
 * @param n
 * @return
 */
ll phi(ll n) {
    int tot = 0;
    for (ll i = 1; i <= n; i++) {
        if (gcd(i, n) == 1) {
           // cerr << i << " ";
            ++tot;
        }
    }
    return tot;
}

int main() {
    long long start = clock();
    cout << phi(2000000) << endl;
    long long end = clock();
    cout << (end - start) << endl;
    return 0;

}